package mao.leetcode.others.leetcode103;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class leetcode103 {
    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(2);
        TreeNode node2 = new TreeNode(3);
        node1.right = node2;
        zigzagLevelOrder(node1);

    }
    /*
     可以使用两个栈实现  s1,s2
     第一层正序访问，只要保证从第二层开始的访问顺序与前一层相反即可
     假设n层已经按照需要的顺序存在于s1：
         s1按照顺序出栈，但是n+1 层确需要与N层不同序访问，所以访问
         n层时可以将n+1层入栈到s2(入栈要考虑先放左节点还是右节点)
     实际实现可以使用一个双向队列，相当于两个栈，一个栈开口向右(s2)，一个栈开口向左(s1)；
    */
    public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        Deque<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> lists = new ArrayList<>();
        if (root == null) return lists;
        boolean reverse = true;
        ArrayList<Integer> l = new ArrayList<>();
        queue.addLast(root);
        TreeNode node;
        while ( !queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                if (reverse){
                    node = queue.pollFirst(); //s1 出栈
                    if (node.left != null) queue.addLast(node.left); //s2入栈
                    if (node.right != null) queue.addLast(node.right);//s2入栈
                    l.add(node.val);
                }else {
                     node = queue.pollLast();   //s2 出栈
                    if (node.right != null) queue.addFirst(node.right);//s1入栈
                    if (node.left != null ) queue.addFirst(node.left);//s1入栈
                    l.add(node.val);
                }
            }
            reverse = !reverse;
            lists.add(l);
            l=new ArrayList<>();
        }
        lists.add(l);  //把最后一个加入进来
        return lists;
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
}
